package com.example.demo.arithmetic.datastructure.tree;

import java.util.Arrays;

/**
 * 根据前序 中序遍历结果构造二叉树
 */
public class Leetcode105 {

    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }
        // 前序第一个节点就是 根结点
        int rootVal = preOrder[0];
        TreeNode root = new TreeNode(rootVal);

        // 中序区分左右字数
        for (int i = 0; i < inOrder.length; i++) {
            if (rootVal == inOrder[i]) {
                // 下标 0到 i-1 左子树
                int[] inLeftTree = Arrays.copyOfRange(inOrder, 0, i);
                // i+1到 length-1 右子树
                int[] inRightTree = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);

                // 拆分前序 和 上面子树长度是一样的
                int[] preLeftTree = Arrays.copyOfRange(preOrder, 1, i + 1);
                int[] preRightTree = Arrays.copyOfRange(preOrder, i + 1, inOrder.length);
                root.left = buildTree(preLeftTree, inLeftTree);
                root.right = buildTree(preRightTree, inRightTree);
                break;
            }
        }
        return root;
    }
}
